rtk 2011

2011.1.1

Vsote

1. podnaloga

Dano je zaporedje $n$ celih števil, recimo jim $a_1, a_2, . . . , a_{n−1}, a_n$. Vsa števila so večja od $0$. Poleg tega je dano tudi celo število $m$.

Naloga

Napiši funkcijo poisci_podzaporedje(seznam,m), ki poišče v tem zaporedju prvo najkrajše tako strnjeno podzaporedje, pri katerem je vsota števil v podzaporedju večja od $m$. Poišče naj torej tak začetni indeks $z$ in dolžino podzaporedja $d$, da bo $a_z + a_{z+1} + a_{z+2} + . . . + a_{z+d−2} + a_{z+d−1} > m$ in da bo $d$ čim manjši. V primeru, da takega pozdaporedja ni, vrni niz "ni primernega podzaporedja"

Vhodni podatki

Dan je seznam $n$ celih števil, recimo jim $a_1, a_2, . . . , a_{n−1}, a_n$. Vsa števila so večja od $0$. Poleg tega je dano tudi celo število $m$.

Izhodni podatki

Par (z,d) z naravnimi števili začetni indeks $z$ (začnemo šteti pri $1$) in dolžino podzaporedja $d$ (če je zaporedju eno število, je to zaporedje dolgo 1)

Primer

Naj bo $m = 24$ in naj bo dan seznam:

   [5, 6, 5, 6, 9, 9, 9, 6]

Najkrajše strnjeno podzaporedje z vsoto, večjo od $m$, je dolgo $3$ člene: $9 + 9 + 9 = 27$, kar je večje od $24$. (Do vsote $25$ pri tem primeru ne moremo priti z nobenim strnjenim podzaporedjem, do vsote $26$ pa sicer lahko, vendar potrebujemo za to vsaj štiri člene: $6 + 5 + 6 + 9 = 26$.) Pravilen rezultat pri tem primeru je torej:

  (5, 3)

Uradna rešitev

def poisci_podzaporedje(seznam,m):
    """Poišče in vrne v tem zaporedju prvo najkrajše tako strnjeno podzaporedje, pri
    katerem je vsota števil v podzaporedju večja od m."""
    zacetni_indeks = -1
    dolzina_seznama = len(seznam)
    dolzina_zaporedja = dolzina_seznama + 1
    for i in range(dolzina_seznama):
        vsota = 0
        for j in range(i, dolzina_seznama):
            vsota += seznam[j]
            if (vsota > m) and (j - i < dolzina_zaporedja):
                zacetni_indeks = i
                dolzina_zaporedja = j - i
                break
    if dolzina_zaporedja > dolzina_seznama:
        return 'ni primernega podzaporedja'
    return (zacetni_indeks + 1, dolzina_zaporedja + 1)

2011.1.3

Majevske številke

1. podnaloga

Maji so ljudstvo, živeče v južni Mehiki in severni Srednji Ameriki s tritisočletno zgodovino. Majevska pisava je bila v rabi vse do prihoda Evropejcev in je dolgo predstavljala veliko zagonetko.

Manj zagoneten pa je njihov sistem zapisa števil. Poznali so ničlo in podobno kot mi (za razliko od rimskih številk) uporabljali mestni zapis števil, vendar s številsko osnovo $20$ (namesto naše bolj običajne $10$). To jim je omogočalo zapisati zelo velika števila, kar je prišlo prav pri obvladovanju astronomije in koledarja.

Posamezne števke torej predstavljajo števila med $0$ in $19$, zapisana pa so kot skupek pik in črt, pri čemer vsaka pika predstavlja $1$ in vsaka črta predstavlja vrednost $5$. Maji so sicer običajno pisali črte ležeče in pike naložene na njih, vendar so lahko črte tudi pokončne in pike lahko ležijo tudi pred ali za njimi — da dobimo vrednost, moramo le pošteti vse črte in pike. Za potrebe te naloge bomo zapisali črto (vrednost $5$) kot znak "|", eno piko kot znak ".", dve piki pa zaradi lepšega izgleda lahko zapišemo kot dvopičje ":" ali pa kot dve piki "..". Števko $0$ so Maji narisali kot školjko, mi pa si bomo pomagali kar z našo ničlo $0$. Nekaj primerov, kako lahko zapišemo posamezne števke:

  0 = 0
  1 = .
  2 = .. ali :
  3 = ... ali :. ali .:
  5 = | ali ::. ali :.: ali .:: ali .....
  8 = .:| ali :|.
  12 = :||
  19 = ::|||

(ali še z nekaj drugimi kombinacijami znakov "|", ":" in ".", ki tu niso naštete)

Števke v mestnem zapisu številke ločimo med seboj s presledkom. Osnova je $20$, na zadnjem mestu je torej faktor $1$, na predzadnjem $20$, na naslednjem z zadnje strani $20 · 20 = 400$, na naslednjem $20 · 20 · 20 = 8000$, itd. Torej povsem enako, kot smo navajeni zapisovati v desetiškem sistemu, le da je faktor $20$ namesto $10$.

Naloga

Napiši funkcijo pretvori_majevsko(niz), ki bo prebral eno majevsko število, zapisano v eni vrstici, kot smo opisali zgoraj (pike, dvopičja in pokončne paličice, presledek loči števke) in izpisal vrednost števila, kot smo navajeni.

Vhodni podatki

Niz z majevsko številko. Za vsako števko je presledek.

Izhodni podatki

Naravno število, pretvorjeno iz majevskega.

Primer

Nekaj primerov večjih števil:

  . 0 = 1 · 20 + 0 · 1 = 20
  : .. = 2 · 20 + 2 · 1 = 42
  | 0 |:| = 5 · 20 · 20 + 0 · 20 + 12 · 1 = 2012
  . | :| | = 1 · 20 · 20 · 20 + 5 · 20 · 20 + 7 · 20 + 5 · 1 = 10145

Uradna rešitev

def pretvori_majevsko(majevsko_stevilo):
    '''Prebere niz, v katerem je zapisana majevska številka,
    jo pretvori v naravno število in vrne'''
    n = 0
    stevka = 0
    for znak in majevsko_stevilo:
        if znak == '0':
            stevka += 0
        elif znak == '.':
            stevka += 1
        elif znak == ':':
            stevka += 2
        elif znak == '|':
            stevka += 5
        else:
            n = 20 * n + stevka
            stevka = 0
    return n

2011.2.1

Vejice

1. podnaloga

Tomija je učiteljica v šoli čisto zastrašila z vejicami: ker so mu v spisih kar naprej manjkale, jih zdaj za vsak slučaj raje napiše malo več. Da jih ja ne bi bilo premalo, postavi kakšno celo sredi besede. Primer njegovega spisa:

  Na t,em vl,a,ku stre,žejo so,uv,laki, ne pa tudi hra,ne,
  bogate z vla,kni,n,ami. Vp,liv lako,,te je, hud!

Ko napiše tak spis v Mikromehki Besedi ali drugem urejevalniku besedil, je zoprno, da ne more enostavno zamenjati vseh pojavitev nekega niza $w1$ z drugim (enako dolgim) nizom $w2$. Če se recimo želi prikupiti svoji učiteljici z Notranjskega in vse pojavitve niza 'vlak' zamenjati z 'wlah', bi moral na koncu dobiti takšno besedilo:

  Na t,em wl,a,hu stre,žejo so,uw,lahi, ne pa tudi hra,ne,
  bogate z wla,hni,n,ami. Vp,liv lako,,te je, hud!

Njegov urejevalnik besedila pa tega ne zna, saj zgago delajo vejice, razmetane znotraj $w1$. Pomagaj ubogemu Tomiju.

Naloga

Napiši funkcijo zamenjaj(s, w1, w2), ki izpiše besedilo, kakršno nastane, če v besedilu s zamenjamo vse pojavitve niza $w1$ z enako dolgim nizom $w2$. Pri teh zamenjavah mora ohraniti vse originalne položaje vejic, kot je tudi prikazano v zgornjem primeru.

Uradna rešitev

def zamenjaj(tekst, niz_1, niz_2):
    pomozni_niz_1 = ''
    indeksiVejic = [i for i, znak in enumerate(tekst) if znak == ',']
    for znak in tekst:
        if znak != ',':
            pomozni_niz_1 += znak

    pomozni_niz_2 = ''
    i = 0
    while i < len(pomozni_niz_1):
        if pomozni_niz_1[i] == niz_1[0] and pomozni_niz_1[i+1] == niz_1[1]:
            pomozni_niz_2 += niz_2
            i += len(niz_2)
        else:
            pomozni_niz_2 += pomozni_niz_1[i]
            i += 1
    koncni_tekst = ''
    i = 0
    while i < len(pomozni_niz_2):
        if i in indeksiVejic:
            koncni_tekst += ','
            indeksiVejic.pop(0);
            pomozni_niz_2 = ' ' + pomozni_niz_2
        else:
            koncni_tekst += pomozni_niz_2[i]
        i += 1
    return koncni_tekst

2011.2.2

(Opomba)

1. podnaloga

Pri pisanju besedila uporabimo oklepaje, če želimo zapisati kakšno opombo (ali kaj drugega manj pomembnega). Včasih tudi znotraj opombe povemo kaj še manj pomembnega (torej manj pomembnega od opombe (ki že sama ni pomembna), a še vedno zanimivega); v takem primeru lahko uporabimo gnezdene oklepaje. Gnezdenje oklepajev lahko načeloma neomejeno stopnjujemo — možno je imeti oklepaje v oklepajih v oklepajih v oklepajih . . . v oklepajih. Če se nam pri branju takšnega teksta mudi, lahko preskočimo vse dele besedila, ki so gnezdeni vsaj k korakov globoko, pri čemer je vrednost k odvisna od tega, kako hudo se nam mudi.

Naloga

Napiši funkcijo samo_pomembno(s, k), ki sprejme niz s s tovrstnim besedilom in naravno število $k$, nato pa vrne niz, na katerem zapišemp kar ostane od besedila $s$, če iz njega pobrišemo vso vsebino, ki je vgnezdena več kot $k$ nivojev globoko.

Primer

Če dobimo naprimer niz $s$:

  '(vse(kar(je(globje,(sdhg((iasgdiasdghbaksbg))) naj)gre)))'

in $k = 4$, naj program vrne niz:

  '(vse(kar(je(globje, naj)gre)))'

Komentar

Naloga je iz 2. tekmovalne skupine, vendar lažja različica.

Uradna rešitev

def samo_pomembno(sez, k):
    '''Prebere niz in ga prepiše v novega, pri čemer spusti vse, kar je z oklepaji
    vgnezdeno globje got k'''
    globina = 0
    rez = ''
    for znak in sez:
        if znak == '(': globina+=1
        if globina <= k: rez += znak
        if znak == ')': globina-=1
    return rez